public class Practice3 {
    //https://leetcode.cn/problems/coin-change-ii/description/
    //动态规划完全背包经典题目
    //非数学证明直接三个for循环
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        dp[0][0] = 1;
        for(int i = 1;i <= n;i++){
            for(int j = 0;j <= amount;j++){
                dp[i][j] += dp[i - 1][j];
                int k = 1;
                while(true){
                    if(j - k * coins[i - 1] >= 0){
                        dp[i][j] += dp[i - 1][j - k * coins[i - 1]];
                        k++;
                    }else{
                        break;
                    }
                }
            }
        }
        return dp[n][amount];
    }
    //数学证明优化
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        dp[0][0] = 1;
        for(int i = 1;i <= n;i++){
            for(int j = 0;j <= amount;j++){
                dp[i][j] += dp[i - 1][j];
                if(j - coins[i - 1] >= 0){
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[n][amount];
    }
    //空间优化
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int x : coins){
            for(int j = 0;j <= amount;j++){
                if(j - x >= 0){
                    dp[j] += dp[j - x];
                }
            }
        }
        return dp[amount];
    }
}
